package com.liunian.algorithmstudy.monotonicstack;

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElements503 {

	/**
	 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
	 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。
	 如果不存在，则输出 -1 。

	 示例 1:
	 输入: nums = [1,2,1]
	 输出: [2,-1,2]
	 解释: 第一个 1 的下一个更大的数是 2；
	 数字 2 找不到下一个更大的数；
	 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

	 示例 2:
	 输入: nums = [1,2,3,4,3]
	 输出: [2,3,4,-1,4]
	 */
	public int[] nextGreaterElements(int[] nums) {
		Stack<Integer> stack = new Stack<>();
		stack.push(0);
		int[] res = new int[nums.length];
		Arrays.fill(res, -1);
		for (int i = 1; i < nums.length * 2; i++) {
			int j = i % nums.length;
			if (nums[j] <= nums[stack.peek()]) {
				stack.push(j);
			} else {
				while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
					Integer pop = stack.pop();
					res[pop] = nums[j];
				}
				stack.push(j);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		NextGreaterElements503 nextGreaterElements = new NextGreaterElements503();
		System.out.println(Arrays.toString(nextGreaterElements.nextGreaterElements(new int[]{1, 2, 1})));
	}

}
